package com.husk.sort;

import com.alibaba.fastjson.JSON;
import org.junit.Test;

/**
 * <p>
 * 快速排序
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/5/12
 */
public class Sort {

    int[] a = new int[]{1, 3, 2, 0, 9, 5, 8, 7};

    @Test
    public void select() {
        // 选择排序
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    this.swap(a, i, j);
                }
            }
        }
        System.out.println(JSON.toJSONString(a));
    }

    @Test
    public void pop() {
        // 冒泡排序
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    this.swap(a, j, j + 1);
                }
            }
        }
        System.out.println(JSON.toJSONString(a));
    }

    @Test
    public void quick() {
        // 快速排序
        this.quick2(a, 0, a.length - 1);
        System.out.println(JSON.toJSONString(a));
    }

    public void quick(int[] array, int low, int high) {
        if (low < high) {
            int i = low, j = high, pivot = array[low];
            while (i < j) {
                while (i < j && array[j] > pivot) {
                    j--;
                }
                if (i < j) {
                    array[i] = array[j];
                    i++;
                }
                while (i < j && array[i] < pivot) {
                    i++;
                }
                if (i < j) {
                    array[j] = array[i];
                    j++;
                }
            }
            array[i] = pivot;
            this.quick(array, low, i - 1);
            this.quick(array, j + 1, high);
        }
    }

    public void quick2(int[] array, int low, int high) {
        if (low < high) {
            int i = low, j = high, pivot = array[low];
            while (i < j) {
                while (i < j && array[j] > pivot) {
                    j--;
                }
                while (i < j && array[i] < pivot) {
                    i++;
                }
                if (i < j && array[i] == array[j]) {
                    i++;
                } else {
                    this.swap(array, i, j);
                }
            }
            this.quick2(array, low, i - 1);
            this.quick2(array, j + 1, high);
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public void heap(int[] array) {
        // 1. 构建大顶堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            // 从第一个非叶子节点从下至上，从右至左调整结构
            this.adjust(array, i, array.length);
        }
        // 2. 调整堆结构+交换堆顶元素与末尾元素
        for (int i = array.length - 1; i > 0; i--) {
            this.swap(array, 0, i); // 将堆顶元素与末尾元素进行交换
            this.adjust(array, 0, i); // 重新对堆进行调整
        }
    }

    public void adjust(int[] array, int i, int length) {
        int temp = array[i]; //先取出当前元素i
        for (int k = i * 2 + 1; i < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
            if (k + 1 < length && array[k] < array[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if (array[k] > temp) { //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                i = k;
                array[i] = array[k];
            } else {
                break;
            }
        }
        array[i] = temp;//将temp值放到最终的位置
    }

}
